package identical_scheduling_algorithm;

import java.util.*;

/**
 * Diese Klasse stellt Methoden bereit, um das Problem MIN BIN PACKING MIT 
 * EINGESCHRÄNKTEN GEWICHTEN mittels eines Dynamischen Programms zu lösen. Es wird dabei der 
 * Algorithmus aus dem Buch ...Jansen verwendet. 
 * 
 * amountPerJob enthält die Anzahl der Jobs vom jeweiligen Typ. 
 * Zunächst muss die Startbelegung generiert werden. Dies geschieht mit dem Aufruf von initialize. 
 * Anschließend kann man mit solve das Dynamische Programm lösen.
 * 
 *  
 * @author Oliver Hense
 * @author Tim Dopke
 *
 */
public class DynamicProgram {
	
	 int amountOfDifferentJobs;
	 double [] amountPerJob;
	 double [] jobSize;
	 double newMakeSpan;
	 ArrayList<int []> A = new ArrayList<int []>();
	 public int [] D;
	 public int [][] helpForSmallJobs;
	 ArrayList<int []> D_ArrayList;
	
	 
	 public DynamicProgram(double [] job, double makeSpan, double delta ){
		 
		 int n = 0;
		 for(int i = 0; i< job.length; i++){
			 if(job[i] != 0)
				 n ++;
		 }
		 this.amountPerJob = new double [n];
		 this.jobSize = new double [n];
		 
		 int j = 0;
		 System.out.println();
		 
	      System.out.println("Große gerundete Jobs nach dem Streichen:");
		 for(int i = 0; i< job.length; i++){
			 if(job[i] != 0){
				 this.amountPerJob[j] = job[i];
				 
				 this.jobSize[j]= delta * Math.pow((1+delta), i);
		    	  System.out.println("Job " +  (j+1) + " mit Jobgroesse "+ jobSize[j]+  " und Anzahl " +job[i]);
				 j++;
			 }
			 
		 }
		 
		 this.amountOfDifferentJobs  = this.amountPerJob.length;
	    
		newMakeSpan = 1+delta;
		 
		 int dLength =1;
		    for(int i = 0; i< this.amountPerJob.length;i++)
		    	dLength = (int)(dLength *(this.amountPerJob[i]+1));
		    D = new int [dLength];
		    helpForSmallJobs = new int[dLength][amountOfDifferentJobs];
		    for(int i = 1; i< D.length; i++)
				D[i] = Integer.MAX_VALUE;
	 }
	
	
	 public  void initialize(){
		 initialize(amountOfDifferentJobs, 0, new LinkedList<Integer>());
	 }
	
	public  void initialize(int m, double wert, LinkedList<Integer> tupel){
		
		if(m == 0){
			
			if(wert <= newMakeSpan){
				//save tupel
				Integer [] help = (Integer[]) tupel.toArray( new Integer[tupel.size()]);
				A.add(toPrimitive(help));	
				
				
				// set value  = 1
				D[kruemelMonster(toPrimitive(help),amountPerJob)] = 1 ;
				
				//Save values for small jobs
				for(int i = 0; i < amountOfDifferentJobs;i++)
				helpForSmallJobs[kruemelMonster(toPrimitive(help),amountPerJob)][i]= 1;
			}
			
		}else{
			
			if(amountPerJob[amountOfDifferentJobs -m] == 0){
				tupel.add(0);
				initialize(m-1, wert ,tupel);
				tupel.removeLast();
			}else{
				
			for(int i=0; i < amountPerJob[amountOfDifferentJobs -m]+1; i++){
				tupel.add(i);
				initialize(m-1, wert + (i*jobSize[amountOfDifferentJobs-m]),tupel);
				tupel.removeLast();
			}
			}
		}
	}
	
	public  void solveDynamicProgram(){
		solveDynamicProgram(amountOfDifferentJobs,new LinkedList<Integer>());
	}
	
	public  void solveDynamicProgram(int m, LinkedList<Integer> tupel){
		
		if(m == 0){
				// save tupel
				Integer [] help = (Integer[]) tupel.toArray( new Integer[tupel.size()] );
				
				// Get next value
				D[kruemelMonster(toPrimitive(help),amountPerJob)] = 1  + findMin(toPrimitive(help));
				
				
			}else{
			
				if(amountPerJob[amountOfDifferentJobs -m] == 0){
					tupel.add(0);
					solveDynamicProgram(m-1 ,tupel);
					tupel.removeLast();
				}else{
		
			for(int i=0; i < amountPerJob[amountOfDifferentJobs -m]+1; i++){
				tupel.add(i);
				solveDynamicProgram(m-1,tupel);
				tupel.removeLast();
			}
			}
		}
	}
	// Get solution for the final occupancy
	public int getSolution(){
		System.out.println("Es werden "+ D[D.length-1] + " Bins benötigt, um das Dynamische Programm zu lösen." );
		return  D[D.length-1];
	}
	
	public  int findMin(int [] j ){
		Iterator<int []> it = A.iterator();
		int[] c= new int[j.length];
		int min = Integer.MAX_VALUE;
		int pos = kruemelMonster(j,amountPerJob);
		while(it.hasNext()){
			int [] a = it.next();
			boolean b = true;
			boolean equal = true;
			for(int i = 0; i< j.length; i++){
				if(a[i] > j[i]){
					b = false;
					equal = false;
				}
				if(a[i] < j[i])
					equal = false;
			}
			if(equal){
				for(int i = 0; i < amountOfDifferentJobs;i++)
					helpForSmallJobs[pos][i]= j[i];
				return 0;
			}
			if(b){
				for(int i =0; i < a.length;i++ )
					c[i] = j[i]- a[i];
				int oldMin = min;
				min = Math.min(min, D[kruemelMonster(c,amountPerJob)]);
				if(oldMin > min)
					for(int i = 0; i < amountOfDifferentJobs;i++)
						helpForSmallJobs[pos][i]= a[i];
			}
			
			
		}
		return min;
		
	}
		
	
 	// Cast Integer array to int array
	public static int[] toPrimitive(Integer[] IntegerArray) { 
		int[] result = new int[IntegerArray.length];
		for (int i = 0; i < IntegerArray.length; i++) {
			result[i] = IntegerArray[i].intValue();
		}
		return result;
	}
	public  void printConfig(){
		printConfig(A);
	}
	public  void printConfig ( ArrayList<int []> a){
		System.out.println();
		for(int i = 0; i< a.size(); i++){
			for(int j = 0 ; j < a.get(i).length; j++)
				System.out.print(a.get(i)[j]+ ", ");
		System.out.println();
		}
		System.out.println();
	}
	
	// mhhh.... nobody knows what the Kruemel Monster is going to do
	public static int kruemelMonster (int [] tupel , double [] amount){
		int pos = 0;
		int multiplikator = 1;
		for(int i =tupel.length-1; i> -1;i --){
			pos = pos +tupel[i]*multiplikator;
			multiplikator = multiplikator * ((int)amount[i]+1);
		}
				
		
		return pos;
	}
	
	//Returns the occupancy of the bins
	public ArrayList<Double> getOccupancy(){
		boolean b = true;
		double m = 0.;
		int pos = D.length-1;
		ArrayList<Double> occupancy = new ArrayList<Double>();
		int[] posHelper = new int[amountOfDifferentJobs];
		for(int j = 0; j<amountOfDifferentJobs; j++ )
			posHelper[j] = (int)amountPerJob[j];
		while(b){
			for(int i = 0; i< amountOfDifferentJobs; i++){
				 m= m + +helpForSmallJobs[pos][i]*jobSize[i];
				posHelper[i] = posHelper[i] -helpForSmallJobs[pos][i];
			}
			occupancy.add(m);
			m = 0.;
			pos = kruemelMonster(posHelper, amountPerJob);
			if(D[pos] == 1)
				b = false;
		}
		for(int i = 0; i< amountOfDifferentJobs; i++){
			 m= m + +helpForSmallJobs[pos][i]*jobSize[i];
		
		
		}
		occupancy.add(m);
		return occupancy;
	}

}
